package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class MinDepthOfBinaryTree111 {
    @Test
    public void test() {
        printMinDepth(Arrays.asList(3,9,20,null,null,15,7));
        printMinDepth(Arrays.asList(2,null,3,null,4,null,5,null,6));
    }

    void printMinDepth(List<Integer> list) {
        TreeNode root = TreeNode.buildTree(list);
        int depth = minDepth(root);
        System.out.format("tree: %s, depth: %d\n", list, depth);
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        int depth = 1;
        while (!q.isEmpty()) {
            // 每次扩张一层, 而不是一个节点, 这样depth就很好计算. 否则要为每个节点记录单独的depth;
            // 先记录每一层的长度, 就是该层的节点数量, 因为后面会变.
            int count = q.size();
            for (int i = 0; i < count; i++) {
                TreeNode node = q.poll();
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    q.offer(node.left);
                }
                if (node.right != null) {
                    q.offer(node.right);
                }
            }
            depth++;
        }
        return depth;
    }
}
